import java.util.ArrayList;
import java.util.List;

class Solution {
    // 申请 下标数组、最终结果数组、辅助下标数组、辅助数据数组
    int[] index;
    int[] ret;
    int[] temp_index;
    int[] temp_nums;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        // 初始化数组
        index = new int[n];
        ret = new int[n];
        temp_index = new int[n];
        temp_nums = new int[n];
        for (int i = 0; i < n; i++) {
            // 逻辑上的绑定
            index[i] = i;
        }

        merge(nums, 0, n-1);

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(ret[i]);
        }
        return list;
    }

    private void merge(int[] nums, int start, int end) {
        // 1、防止越界
        if (start >= end) {
            return;
        }
        // 2、处理左侧数据、处理右侧数据
        int mid = (start+end) / 2;
        merge(nums, start, mid);
        merge(nums, mid+1, end);
        // 3、处理一左一右的情况
        int left = start, right = mid+1, i = 0;
        while (left <= mid && right <= end) { // 进行降序排序
            if (nums[left] <= nums[right]) { // 不符合要求，直接排序即可
                // 既要把基本的数据排序，也要对绑定的下标排序
                temp_nums[i] = nums[right];
                temp_index[i++] = index[right++];
            } else {
                // 统计对应下标的数据（这里一定得是原始下标）
                ret[index[left]] += (end-right+1);
                // 继续进行排序
                temp_nums[i] = nums[left];
                temp_index[i++] = index[left++];
            }
        }
        
        while (left <= mid) {
            temp_nums[i] = nums[left];
            temp_index[i++] = index[left++];
        }
        
        while (right <= end) {
            temp_nums[i] = nums[right];
            temp_index[i++] = index[right++];
        }
        // 4、处理剩下的排序
        for (int j = start; j <= end; j++) {
            // 基本数据 + 下标
            nums[j] = temp_nums[j-start];
            index[j] = temp_index[j-start];
        }
    }
}